\documentclass{beamer}
\usepackage[utf8]{inputenc}
\beamertemplateshadingbackground{red!10}{blue!10}
%\usepackage{fancybox}
\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{url}
%\usepackage{graphics}
%\usepackage{xcolor}
\usepackage{fancybox}
\usepackage{moreverb}
%\usepackage[all]{xy}
\usepackage{listings}
\usepackage{filecontents}
\usepackage{graphicx}

\lstset{
  language=Lisp,
  basicstyle=\scriptsize\ttfamily,
  keywordstyle={},
  commentstyle={},
  stringstyle={}}

\def\inputfig#1{\input #1}
\def\inputeps#1{\includegraphics{#1}}
\def\inputtex#1{\input #1}

\inputtex{logos.tex}

%\definecolor{ORANGE}{named}{Orange}

\definecolor{GREEN}{rgb}{0,0.8,0}
\definecolor{YELLOW}{rgb}{1,1,0}
\definecolor{ORANGE}{rgb}{1,0.647,0}
\definecolor{PURPLE}{rgb}{0.627,0.126,0.941}
\definecolor{PURPLE}{named}{purple}
\definecolor{PINK}{rgb}{1,0.412,0.706}
\definecolor{WHEAT}{rgb}{1,0.8,0.6}
\definecolor{BLUE}{rgb}{0,0,1}
\definecolor{GRAY}{named}{gray}
\definecolor{CYAN}{named}{cyan}

\newcommand{\orchid}[1]{\textcolor{Orchid}{#1}}
\newcommand{\defun}[1]{\orchid{#1}}

\newcommand{\BROWN}[1]{\textcolor{BROWN}{#1}}
\newcommand{\RED}[1]{\textcolor{red}{#1}}
\newcommand{\YELLOW}[1]{\textcolor{YELLOW}{#1}}
\newcommand{\PINK}[1]{\textcolor{PINK}{#1}}
\newcommand{\WHEAT}[1]{\textcolor{wheat}{#1}}
\newcommand{\GREEN}[1]{\textcolor{GREEN}{#1}}
\newcommand{\PURPLE}[1]{\textcolor{PURPLE}{#1}}
\newcommand{\BLACK}[1]{\textcolor{black}{#1}}
\newcommand{\WHITE}[1]{\textcolor{WHITE}{#1}}
\newcommand{\MAGENTA}[1]{\textcolor{MAGENTA}{#1}}
\newcommand{\ORANGE}[1]{\textcolor{ORANGE}{#1}}
\newcommand{\BLUE}[1]{\textcolor{BLUE}{#1}}
\newcommand{\GRAY}[1]{\textcolor{gray}{#1}}
\newcommand{\CYAN}[1]{\textcolor{cyan }{#1}}

\newcommand{\reference}[2]{\textcolor{PINK}{[#1~#2]}}
%\newcommand{\vect}[1]{\stackrel{\rightarrow}{#1}}

% Use some nice templates
\beamertemplatetransparentcovereddynamic

\newcommand{\A}{{\mathbb A}}
\newcommand{\degr}{\mathrm{deg}}

\title{Creating a \commonlisp{} implementation\\(Part 3)}

\author{Robert Strandh}
\institute{
}
\date{September, 2020}

%\inputtex{macros.tex}

\begin{document}
\frame{
\titlepage
}

\setbeamertemplate{footline}{
\vspace{-1em}
\hspace*{1ex}{~} \GRAY{\insertframenumber/\inserttotalframenumber}
}

\frame{
\frametitle{Topics covered in presentation series}
\vskip 0.25cm
\begin{itemize}
\item Choices of implementation language.
\item Implementation strategies for the evaluator.
\item Division of code written in \commonlisp{} and code written in
  the implementation language.
\end{itemize}
}

\frame{
\frametitle{Topics not covered in presentation series}
\vskip 0.25cm
\begin{itemize}
\item How a \commonlisp{} compiler works.  If there is a demand, maybe
  in a different series.
\item How different strategies for memory management work.
\item Details about how an abstract machine could work.
\item Details about how a typical concrete processor works.
\end{itemize}
\vskip 0.25cm
Interest for some of these topics has been expressed.  We may create
talks on these topics in the future.
}

\frame{
\frametitle{General assumptions (from Part 1)}
\vskip 0.25cm
\begin{itemize}
\item We want to use \commonlisp{} as much as possible for the
  implementation.
\item The resulting system should not be too slow, but we do not
  need extremely good performance.
\item The implementation we are creating has no classes and no generic
  functions.  This assumption will be
  revisited later.
\end{itemize}
}

\frame{
\frametitle{Strategy 1: Start with a small core in (say) C}
\vskip 0.25cm
\begin{itemize}
\item Write a minimal subset in an existing language.
\item Add more and more functionality, written in \commonlisp{}.
\end{itemize}
}

\frame[containsverbatim]{
\frametitle{Strategy 1: Complications}
\vskip 0.25cm
Summary of problems:
\vskip 0.25cm
\begin{itemize}
\item We end up with a lot of C code, despite our best intentions.
\item We may end up with multiple versions of the same module, one
  (simplified) C version, and one (complete) \commonlisp{} version.
\item Much of the \commonlisp{} code is not written in the most
  ``natural'' way.
\item There are many, often implicit, dependencies between modules.
\item The resulting system is hard to maintain, especially when
  dependencies are implicit.
\end{itemize}
}

\frame[containsverbatim]{
\frametitle{Circular compile-time dependencies}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-full-example-from-part-1.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Abstract machine}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-abstract-machine-1.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{What can be done?}
}

\frame{
\frametitle{Hypothetical situation}
\vskip 0.25cm
Let us imagine the following scenario:
\vskip 0.25cm
\begin{itemize}
\item We have managed to write a conforming \commonlisp{} implementation.
\item We wrote an evaluator in C, as a direct interpreter.
\item The result is slow, so now we want to write a bytecode compiler.
\item Since we have a working \commonlisp{} implementation, we can
  write it in \commonlisp{}.
\end{itemize}
\vskip 0.25cm
This bytecode compiler is the core of strategy 2.
}

\frame{
\frametitle{\commonlisp{} file compiler}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-common-lisp-file-compilation.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Contents of output file}
\vskip 0.25cm
The output file contains elements from three sources:
\vskip 0.25cm
\begin{enumerate}
\item From the code in the input file: Names of functions, variables, etc.
\item From the code generator of the compiler: Instructions, lexical locations, etc.
\item From macros in the startup environment: Names of functions,
  variables, etc. that the macro expander generated.
\end{enumerate}
\vskip 0.25cm
The definitions of the macros are specific to the \commonlisp{}
implementation.
}

\frame{
\frametitle{Compiler for a traditional batch language}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-c-unix-1.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Essential difference}
\vskip 0.25cm
This difference between the two types of languages is crucial:
\vskip 0.25cm
\begin{enumerate}
\item A compiler for a batch language can run anywhere.
\item Because of the macros, a \commonlisp{} compiler must in
  principle be executed from the very \commonlisp{} system that it is
  written for.
\end{enumerate}
\vskip 0.25cm
Aside from that pesky little problem, a \commonlisp{} compiler can be
written in portable \commonlisp{} and can thus be executed from any
conforming \commonlisp{} implementation.
}

\frame{
\frametitle{What if a solution existed?}
\vskip 0.25cm
Imagine we found a solution to that pesky little problem.
\vskip 0.25cm
\begin{itemize}
\item We could execute the compiler on a \emph{host} \commonlisp{}
  system. 
\item We could feed the source of the compiler as input files.
\item We would then have the compiler, compiled to bytecodes.
\item With a simple bytecode loader, written in C, we could then load
  the compiled compiler.
\item And there is no longer any need for our initial interpreter.
\end{itemize}
\vskip 0.25cm
This is the essence of \emph{cross compilation}.
}

\frame[containsverbatim]{
\frametitle{Typical native package structure}
\begin{verbatim}
(defpackage #:common-lisp
  (:use)
  (:export #:car #:cdr ... #:mapcar))
---
(defpackage #:target-cons
  (:use #:common-lisp))
---
(in-package #:target-cons)

(defun mapcar (fun list)
  ...)
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Example file to compile}
\begin{verbatim}
(in-package #:target-cons)

(defun mapcar (function list)
  (do ((sublist list (rest sublist))
       (result '()))
      ((null sublist) (nreverse result))
    (push (funcall function (first sublist))
          result)))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Package structure for cross compilation}
\begin{verbatim}
(defpackage #:target-common-lisp
  ...
  ...
---
(defpackage #:target-cons
  (:use #:target-common-lisp))
---
(in-package #:target-cons)

(defun mapcar (fun list)
  ...)
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{ASDF system definition for cross compilation}
\begin{verbatim}
(cl:in-package #:asdf-user)

(defsystem #:target
  :depends-on (#:cleavir-code-utilities)
  :serial t
  :components
  ((:file "target-common-lisp-package")
   (:file "target-cons-package")
   (:file "target-evaluation-and-compilation-package")
   (:file "target-data-and-control-flow-package")
   (:file "load-target-macros")))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Package structure for cross compilation}
\begin{verbatim}
(cl:in-package #:common-lisp-user)

(defpackage #:target-cons
  (:use #:target-common-lisp))
---
(cl:in-package #:common-lisp-user)

(defpackage #:target-data-and-control-flow
  (:use #:target-common-lisp))
---
(cl:in-package #:common-lisp-user)

(defpackage #:target-evaluation-and-compilation
  (:use #:target-common-lisp))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{The \texttt{target-common-lisp} package}
{\small\begin{verbatim}
(cl:in-package #:common-lisp-user)

(defpackage #:target-common-lisp
  (:use)
  (:import-from #:common-lisp
     .
     #.(let ((result '()))
         (do-external-symbols (symbol (find-package '#:cl))
           (when (or (member symbol lambda-list-keywords)
                     (special-operator-p symbol))
             (push (symbol-name symbol) result)))
         result))
  (:export
   .
   #.(let ((result '()))
       (do-external-symbols (symbol (find-package '#:cl))
         (push (symbol-name symbol) result))
       result)))
\end{verbatim}
}
}

\frame[containsverbatim]{
\frametitle{Load target macros}
{\small\begin{verbatim}
(cl:in-package #:common-lisp-user)

(defun load-target-macros ()
  (setf (macro-function 'target-common-lisp:defmacro)
        (macro-function 'defmacro))
  (do-external-symbols (symbol (find-package '#:common-lisp))
    (when (and (fboundp symbol)
               (null (macro-function symbol))
               (not (special-operator-p symbol)))
      (setf (fdefinition (find-symbol (symbol-name symbol)
                                      '#:target-common-lisp))
                         (fdefinition symbol)))
    ... [same for (setf <foo>) functions] 
  (load "defmacro-defmacro.lisp")
  (load "lambda-defmacro.lisp")
  (load "return-defmacro.lisp")
  (load "when-defmacro.lisp")
  ...)
\end{verbatim}
}
}

\frame[containsverbatim]{
\frametitle{Load target macros}
{\small\begin{verbatim}
(cl:in-package #:target-evaluation-and-compilation)

(defmacro defmacro (name lambda-list &body body)
  `(setf (macro-function ',name)
         ,(cleavir-code-utilities:parse-macro
            name lambda-list body)))
\end{verbatim}
}
\vskip 0.25cm
The \texttt{parse-macro} function is from CLtL2, and can be written in
portable \commonlisp{}.
}

\frame[containsverbatim]{
\frametitle{Load target macros}
{\small\begin{verbatim}
(cl:in-package #:target-evaluation-and-compilation)

(defmacro lambda (lambda-list &body body)
  `(function (lambda ,lambda-list ,@body)))
\end{verbatim}
}
}

\frame[containsverbatim]{
\frametitle{Load target macros}
{\small\begin{verbatim}
(cl:in-package #:target-data-and-control-flow)

(defmacro return (&optional (form nil))
  `(return-from nil ,form))
\end{verbatim}
}
}

\frame[containsverbatim]{
\frametitle{Load target macros}
{\small\begin{verbatim}
(cl:in-package #:target-data-and-control-flow)

(defmacro when (test &body body)
  `(if ,test (progn ,@body) nil))
\end{verbatim}
}
}

\frame{
\frametitle{Minor issues}
\vskip 0.25cm
The compiled files will refer to package \texttt{target-common-lisp}
rather than to \texttt{common-lisp}.
\vskip 0.25cm
To handle that issue, when the compiled file is loaded into the target
system, make \texttt{target-common-lisp} a nickname of the package
\texttt{common-lisp}.
\vskip 0.25cm
Target-specific function executed by target macro expanders must also
be loaded on the host.
}

\frame{
\frametitle{What we have accomplished}
\vskip 0.25cm
We can compile any target code on the host.
\vskip 0.25cm
And \emph{any} includes the evaluator and the reader.
\vskip 0.25cm
The only C code left is the bytecode interpreter and the abstract
machine.
}

\frame{
\frametitle{We can do even better}
\vskip 0.25cm
We don't have to compile to bytecodes.  We can compile to native
code.
\vskip 0.25cm
Building the target system from compiled files can be a bit tricky,
but it can be done.
\vskip 0.25cm
This technique is essentially what SBCL uses for its bootstrapping
procedure.
}

\frame{
\frametitle{Topics for part 4}
\vskip 0.25cm
Recall that we are creating a pre-ANSI \commonlisp{} implementation,
so it has no classes and no generic functions.
\vskip 0.25cm
In part 4, we examine the impact on our implementation of not having
CLOS from the start.
}

\end{document}
